1. Field of the Invention
This invention generally relates to a multiplying device for calculating the product of multiplicand data and multiplier data. This invention particularly relates to a multiplying device which uses Booth's algorithm for generating partial products.
2. Description of the Related Art
In recent years, digital signal processing apparatuses have been required to operate at higher speeds. Each digital signal processing apparatus is composed of parts including multiplying devices (multipliers). High-speed operation of multiplying devices has been desired.
A general multiplying device (a general multiplier) includes a partial product generating circuit and an adding circuit. The partial product generating circuit responds to data representing a multiplicand and data representing a multiplier. The data representing the multiplicand is also referred to as the multiplicand data. In some cases, the multiplicand data is shortened to the multiplicand. The data representing the multiplier is also referred to as the multiplier data. In some cases, the multiplier data is shortened to the multiplier. The partial product generating circuit produces data pieces representative of respective partial products in response to the multiplicand data and the multiplier data. The adding circuit adds the partial product data pieces to generate data representing the final product of the multiplicand and the multiplier. The adding circuit outputs the final product data. As the number of partial products increases, the speed of operation of the adding circuit drops so that the speed of product calculation by the multiplying device also drops.
Booth's algorithm is a method of reducing the number of partial products in a partial product generation stage. Booth's algorithm features that multiplication in a two's complement representation form can be executed without any correction. According to second-order Booth's algorithm, the number of partial products can be reduced to half the number of those required in straight combinatorial multipliers. Thus, in a multiplying device using second-order Booth's algorithm to generate partial products, a stage of adding the partial products can be short, and therefore the speed of multiplication can be high.
In a prior-art multiplying device, adders in a stage preceding a final adding stage are different from each other in number of bits of input data to be added. In the case where such adders are formed by a semiconductor integrated circuit, different bit numbers of the adders are inconvenient for chip layout.